package problem.ejercicio2;

import java.util.Vector;

public class Red {
	
	private Cola path;
	
	
	public int run(String p, String q, Vector<Amistad> amistades){
		
		/// PARTE1 : Genera un vector con todos los investigadores
		Vector<String> investigadores = new Vector<String>();
		int i,j;
		if(amistades.size() == 0) return 0;
		for(i=0;i<amistades.size();i++){								
			if(!investigadores.contains(amistades.get(i).primero())){
				investigadores.add(amistades.get(i).primero());				
			}
			if(!investigadores.contains(amistades.get(i).segundo())){
				investigadores.add(amistades.get(i).segundo());
			}			
		}
		
		 /// PARTE2 : Esto me genera el grafo
		Vector<Relaciones> grafo = new Vector<Relaciones>(); 
		for(i=0;i<investigadores.size();i++){
			String inv = investigadores.get(i);
			grafo.add(i,Relaciones.Nuevo(inv,0,0));
			for(j=0;j<amistades.size();j++){
				if(inv.equals(amistades.get(j).primero())){
					grafo.get(i).hijos().add(amistades.get(j).segundo());
				}
				if(inv.equals(amistades.get(j).segundo())){
					grafo.get(i).hijos().add(amistades.get(j).primero());
				}
					
			}						
		}
		
		/// PARTE 3: Empiezo la busqueda del resultado
		
		i = buscarString(q,grafo);
		if( i > grafo.size()-1) return 0;		
		
		// Aca tengo el i el indice por donde empezar
		int respuesta = BuscarResultado(p,q,i,grafo);
		
		return respuesta;
	}
	
	// Busqueda a lo ancho sobre el grafo
	private int BuscarResultado(String p, String q, int i,Vector<Relaciones> vr){
		int j;	
		vr.get(i).modFlag(1);
		path = Cola.Nuevo();
		path.encolar(vr.get(i));
		while(!path.vacio()){
			Relaciones nodo = path.desencolar();			
			if(nodo.nombre().equals(p)){
				return nodo.altura();
			}
			if(nodo.hijos().size() != 0){
				for(j=0;j<nodo.hijos().size();j++){
					int posicion = buscarString(nodo.hijos().get(j),vr);
					if(vr.get(posicion).flag() == 0){
						vr.get(posicion).modFlag(1);
						vr.get(posicion).modAltura(nodo.altura()+1);
						path.encolar(vr.get(posicion));					
					}				
				}
			}						
		}
		return 0;
	}
		
	// Buscar el string S en el vector
	private int buscarString(String s,Vector<Relaciones> vr){
		int i;
		for(i=0;i<vr.size();i++){
			if(s.equals(vr.get(i).nombre())){
				break;
			}
		}
		return i;
	}		
}
